//题目描述
//给一个能承重V的背包，和n件物品，我们用重量和价值的二元组来表示一个物品，
//第i件物品表示为（Vi，Wi），问：在背包不超重的情况下，得到物品的最大价值是多少？
//样例输入1
// 15 4
// 4 10
// 3 7
// 12 12
// 9 8
#include <iostream>
using namespace std;

#define MAX_N 100
#define MAX_V 10000
int v[MAX_N + 5], w[MAX_N + 5];
int dp[MAX_V + 5] = {0};

int main()
{
    int V, n;
    cin >> V >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> v[i] >> w[i];
    }
    for(int i = 1; i <= n; i++)
    {
        for(int j = V; j >= 0; j--)
        {
            if(j < v[i]) continue;
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }
    cout << dp[V];
    return 0;
}